home *** CD-ROM | disk | FTP | other *** search
/ STraTOS 1997 April & May / STraTOS 1 - 1997 April & May.iso / CD01 / INTERNET / SITES / LITTLE / P3SRC.ZIP / ATARI / VLBUFFER.C < prev    next >
Encoding:
C/C++ Source or Header  |  1996-04-12  |  13.0 KB  |  605 lines
  1. /****************************************************************************
  2. *                   vlbuffer.c
  3. *
  4. *  This module implements functions that are used by the vista/light buffer.
  5. *
  6. *  This module was written by Dieter Bayer [DB].
  7. *
  8. *  from Persistence of Vision(tm) Ray Tracer
  9. *  Copyright 1996 Persistence of Vision Team
  10. *---------------------------------------------------------------------------
  11. *  NOTICE: This source code file is provided so that users may experiment
  12. *  with enhancements to POV-Ray and to port the software to platforms other
  13. *  than those supported by the POV-Ray Team.  There are strict rules under
  14. *  which you are permitted to use this file.  The rules are in the file
  15. *  named POVLEGAL.DOC which should be distributed with this file. If
  16. *  POVLEGAL.DOC is not available or for more info please contact the POV-Ray
  17. *  Team Coordinator by leaving a message in CompuServe's Graphics Developer's
  18. *  Forum.  The latest version of POV-Ray may be found there as well.
  19. *
  20. * This program is based on the popular DKB raytracer version 2.12.
  21. * DKBTrace was originally written by David K. Buck.
  22. * DKBTrace Ver 2.0-2.12 were written by David K. Buck & Aaron A. Collins.
  23. *
  24. *****************************************************************************/
  25.  
  26. /****************************************************************************
  27. *
  28. *  Explanation:
  29. *
  30. *    -
  31. *
  32. *  ---
  33. *
  34. *  Mar 1994 : Creation.
  35. *
  36. *****************************************************************************/
  37.  
  38. #include "frame.h"
  39. #include "vector.h"
  40. #include "povproto.h"
  41. #include "bbox.h"
  42. #include "vlbuffer.h"
  43.  
  44.  
  45.  
  46. /*****************************************************************************
  47. * Local preprocessor defines
  48. ******************************************************************************/
  49.  
  50. #define INITIAL_NUMBER_OF_ENTRIES 256
  51.  
  52.  
  53. /*****************************************************************************
  54. * Local typedefs
  55. ******************************************************************************/
  56.  
  57.  
  58.  
  59. /*****************************************************************************
  60. * Local variables
  61. ******************************************************************************/
  62.  
  63. /* Tree node queue. */
  64.  
  65. PROJECT_QUEUE *Node_Queue;
  66.  
  67. /* Priority queue. */
  68.  
  69. PRIORITY_QUEUE *VLBuffer_Queue;
  70.  
  71.  
  72.  
  73. /*****************************************************************************
  74. * Static functions
  75. ******************************************************************************/
  76.  
  77.  
  78.  
  79. /*****************************************************************************
  80. *
  81. * FUNCTION
  82. *
  83. *   Initialize_VLBuffer_Code
  84. *
  85. * INPUT
  86. *   
  87. * OUTPUT
  88. *   
  89. * RETURNS
  90. *   
  91. * AUTHOR
  92. *
  93. *   Dieter Bayer
  94. *   
  95. * DESCRIPTION
  96. *
  97. *   Init queues used by the light and vista buffer.
  98. *
  99. * CHANGES
  100. *
  101. *   May 1994 : Creation.
  102. *
  103. ******************************************************************************/
  104.  
  105. void Initialize_VLBuffer_Code()
  106. {
  107.   Node_Queue = (PROJECT_QUEUE *)POV_MALLOC(sizeof(PROJECT_QUEUE),
  108.     "vista/light buffer node queue");
  109.  
  110.   Node_Queue->QSize = 0;
  111.  
  112.   Node_Queue->Max_QSize = INITIAL_NUMBER_OF_ENTRIES;
  113.  
  114.   Node_Queue->Queue = (PROJECT_TREE_NODE **)POV_MALLOC(Node_Queue->Max_QSize*sizeof(PROJECT_TREE_NODE *),
  115.     "vista/light buffer node queue");
  116.  
  117.   VLBuffer_Queue = Create_Priority_Queue(INITIAL_NUMBER_OF_ENTRIES);
  118. }
  119.  
  120.  
  121.  
  122. /*****************************************************************************
  123. *
  124. * FUNCTION
  125. *
  126. *   Reinitialize_VLBuffer_Code
  127. *
  128. * INPUT
  129. *   
  130. * OUTPUT
  131. *   
  132. * RETURNS
  133. *   
  134. * AUTHOR
  135. *
  136. *   Dieter Bayer
  137. *   
  138. * DESCRIPTION
  139. *
  140. *   Reinit queues used by the light and vista buffer.
  141. *
  142. *   Note that only the node queue needs to be reinitialized.
  143. *
  144. * CHANGES
  145. *
  146. *   Feb 1995 : Creation.
  147. *
  148. ******************************************************************************/
  149.  
  150. void Reinitialize_VLBuffer_Code()
  151. {
  152.   if (Node_Queue->QSize >= Node_Queue->Max_QSize)
  153.   {
  154.     if (Node_Queue->QSize >= INT_MAX/2)
  155.     {
  156.       Error("Node queue overflow.\n");
  157.     }
  158.  
  159.     Node_Queue->Max_QSize *= 2;
  160.  
  161.     Node_Queue->Queue = (PROJECT_TREE_NODE **)POV_REALLOC(Node_Queue->Queue,
  162.       Node_Queue->Max_QSize*sizeof(PROJECT_TREE_NODE *),
  163.       "vista/light buffer node queue");
  164.   }
  165. }
  166.  
  167.  
  168.  
  169. /*****************************************************************************
  170. *
  171. * FUNCTION
  172. *
  173. *   Deinitialize_VLBuffer_Code
  174. *
  175. * INPUT
  176. *   
  177. * OUTPUT
  178. *   
  179. * RETURNS
  180. *   
  181. * AUTHOR
  182. *
  183. *   Dieter Bayer
  184. *   
  185. * DESCRIPTION
  186. *
  187. *   Deinit queues used by the light and vista buffer.
  188. *
  189. * CHANGES
  190. *
  191. *   May 1994 : Creation.
  192. *
  193. ******************************************************************************/
  194.  
  195. void Deinitialize_VLBuffer_Code()
  196. {
  197.   if (Node_Queue != NULL)
  198. {
  199.     POV_FREE(Node_Queue->Queue);
  200.  
  201.     POV_FREE(Node_Queue);
  202.   }
  203.  
  204.   if (VLBuffer_Queue != NULL)
  205.   {
  206.     Destroy_Priority_Queue(VLBuffer_Queue);
  207.   }
  208.  
  209.   Node_Queue     = NULL;
  210.   VLBuffer_Queue = NULL;
  211. }
  212.  
  213.  
  214.  
  215. /*****************************************************************************
  216. *
  217. * FUNCTION
  218. *
  219. *   Clip_Polygon
  220. *
  221. * INPUT
  222. *
  223. *   Points             - polygon's points
  224. *   PointCnt           - Number of points in polygon
  225. *   VX1, VY1, VX2, VY1 - Normal vectors of the clipping planes
  226. *   DX1, DY1, DX2, DY2 - Distances of the clipping planes from
  227. *   the origin
  228. *   
  229. * OUTPUT
  230. *
  231. *   Points, PointCnt
  232. *   
  233. * RETURNS
  234. *   
  235. * AUTHOR
  236. *
  237. *   Dieter Bayer
  238. *   
  239. * DESCRIPTION
  240. *
  241. *   Clip polygon at the viewing pyramid define by the normal vectors
  242. *   VX1, VX2, VY1, VY2 and the distances DX1, DX2, DY1, DY2.
  243. *
  244. * CHANGES
  245. *
  246. *   May 1994 : Creation.
  247. *
  248. ******************************************************************************/
  249.  
  250. void Clip_Polygon(Points, PointCnt, VX1, VX2, VY1, VY2, DX1, DX2, DY1, DY2)
  251. VECTOR *Points;
  252. int *PointCnt;
  253. VECTOR VX1, VX2, VY1, VY2;
  254. DBL DX1, DX2, DY1, DY2;
  255. {
  256.   DBL aktd, pred, fird, k;
  257.   VECTOR aktP, intP, preP, firP, d;
  258.   int i, pc;
  259.   VECTOR ClipPoints[MAX_CLIP_POINTS];
  260.  
  261.   /********** clip polygon at "left" plane **********/
  262.  
  263.   pc = 0;
  264.  
  265.   Assign_Vector(firP, Points[0]);
  266.  
  267.   fird = VX1[X] * firP[X] + VX1[Y] * firP[Y] + VX1[Z] * firP[Z] - DX1;
  268.  
  269.   if (fird <= 0.0)
  270.   {
  271.     Assign_Vector(ClipPoints[pc++], firP);
  272.   }
  273.  
  274.   Assign_Vector(aktP, firP);
  275.   Assign_Vector(preP, firP);
  276.  
  277.   aktd = pred = fird;
  278.  
  279.   for (i = 1; i < *PointCnt; i++)
  280.   {
  281.     Assign_Vector(aktP, Points[i]);
  282.  
  283.     aktd = VX1[X] * aktP[X] + VX1[Y] * aktP[Y] + VX1[Z] * aktP[Z] - DX1;
  284.  
  285.     if (((aktd < 0.0) && (pred > 0.0)) || ((aktd > 0.0) && (pred < 0.0)))
  286.     {
  287.       d[X] = preP[X] - aktP[X];
  288.       d[Y] = preP[Y] - aktP[Y];
  289.       d[Z] = preP[Z] - aktP[Z];
  290.  
  291.       k = -aktd / (VX1[X] * d[X] + VX1[Y] * d[Y] + VX1[Z] * d[Z]);
  292.  
  293.       intP[X] = aktP[X] + k * d[X];
  294.       intP[Y] = aktP[Y] + k * d[Y];
  295.       intP[Z] = aktP[Z] + k * d[Z];
  296.  
  297.       Assign_Vector(ClipPoints[pc++], intP);
  298.     }
  299.  
  300.     if (aktd <= 0.0)
  301.     {
  302.       Assign_Vector(ClipPoints[pc++], aktP);
  303.     }
  304.  
  305.     Assign_Vector(preP, aktP);
  306.  
  307.     pred = aktd;
  308.   }
  309.  
  310.   if (((fird < 0.0) && (aktd > 0.0)) || ((fird > 0.0) && (aktd < 0.0)))
  311.   {
  312.     d[X] = firP[X] - aktP[X];
  313.     d[Y] = firP[Y] - aktP[Y];
  314.     d[Z] = firP[Z] - aktP[Z];
  315.  
  316.     k = -aktd / (VX1[X] * d[X] + VX1[Y] * d[Y] + VX1[Z] * d[Z]);
  317.  
  318.     intP[X] = aktP[X] + k * d[X];
  319.     intP[Y] = aktP[Y] + k * d[Y];
  320.     intP[Z] = aktP[Z] + k * d[Z];
  321.  
  322.     Assign_Vector(ClipPoints[pc++], intP);
  323.   }
  324.  
  325.   for (i = 0; i < pc; i++)
  326.   {
  327.     Assign_Vector(Points[i], ClipPoints[i]);
  328.   }
  329.  
  330.   if ((*PointCnt = pc) == 0)
  331.     return;
  332.  
  333.   /********** clip polygon at "right" plane **********/
  334.  
  335.   pc = 0;
  336.  
  337.   Assign_Vector(firP, Points[0]);
  338.  
  339.   fird = VX2[X] * firP[X] + VX2[Y] * firP[Y] + VX2[Z] * firP[Z] - DX2;
  340.  
  341.   if (fird <= 0.0)
  342.   {
  343.     Assign_Vector(ClipPoints[pc++], firP);
  344.   }
  345.  
  346.   Assign_Vector(aktP, firP);
  347.   Assign_Vector(preP, firP);
  348.  
  349.   aktd = pred = fird;
  350.  
  351.   for (i = 1; i < *PointCnt; i++)
  352.   {
  353.     Assign_Vector(aktP, Points[i]);
  354.  
  355.     aktd = VX2[X] * aktP[X] + VX2[Y] * aktP[Y] + VX2[Z] * aktP[Z] - DX2;
  356.  
  357.     if (((aktd < 0.0) && (pred > 0.0)) || ((aktd > 0.0) && (pred < 0.0)))
  358.     {
  359.       d[X] = preP[X] - aktP[X];
  360.       d[Y] = preP[Y] - aktP[Y];
  361.       d[Z] = preP[Z] - aktP[Z];
  362.  
  363.       k = -aktd / (VX2[X] * d[X] + VX2[Y] * d[Y] + VX2[Z] * d[Z]);
  364.  
  365.       intP[X] = aktP[X] + k * d[X];
  366.       intP[Y] = aktP[Y] + k * d[Y];
  367.       intP[Z] = aktP[Z] + k * d[Z];
  368.  
  369.       Assign_Vector(ClipPoints[pc++], intP);
  370.     }
  371.  
  372.     if (aktd <= 0.0)
  373.     {
  374.       Assign_Vector(ClipPoints[pc++], aktP);
  375.     }
  376.  
  377.     Assign_Vector(preP, aktP);
  378.  
  379.     pred = aktd;
  380.   }
  381.  
  382.   if (((fird < 0.0) && (aktd > 0.0)) || ((fird > 0.0) && (aktd < 0.0)))
  383.   {
  384.     d[X] = firP[X] - aktP[X];
  385.     d[Y] = firP[Y] - aktP[Y];
  386.     d[Z] = firP[Z] - aktP[Z];
  387.  
  388.     k = -aktd / (VX2[X] * d[X] + VX2[Y] * d[Y] + VX2[Z] * d[Z]);
  389.  
  390.     intP[X] = aktP[X] + k * d[X];
  391.     intP[Y] = aktP[Y] + k * d[Y];
  392.     intP[Z] = aktP[Z] + k * d[Z];
  393.  
  394.     Assign_Vector(ClipPoints[pc++], intP);
  395.   }
  396.  
  397.   for (i = 0; i < pc; i++)
  398.   {
  399.     Assign_Vector(Points[i], ClipPoints[i]);
  400.   }
  401.  
  402.   if ((*PointCnt = pc) == 0)
  403.     return;
  404.  
  405.   /********** clip polygon at "bottom" plane **********/
  406.  
  407.   pc = 0;
  408.  
  409.   Assign_Vector(firP, Points[0]);
  410.  
  411.   fird = VY1[X] * firP[X] + VY1[Y] * firP[Y] + VY1[Z] * firP[Z] - DY1;
  412.  
  413.   if (fird <= 0.0)
  414.   {
  415.     Assign_Vector(ClipPoints[pc++], firP);
  416.   }
  417.  
  418.   Assign_Vector(aktP, firP);
  419.   Assign_Vector(preP, firP);
  420.  
  421.   aktd = pred = fird;
  422.  
  423.   for (i = 1; i < *PointCnt; i++)
  424.   {
  425.     Assign_Vector(aktP, Points[i]);
  426.  
  427.     aktd = VY1[X] * aktP[X] + VY1[Y] * aktP[Y] + VY1[Z] * aktP[Z] - DY1;
  428.  
  429.     if (((aktd < 0.0) && (pred > 0.0)) || ((aktd > 0.0) && (pred < 0.0)))
  430.     {
  431.       d[X] = preP[X] - aktP[X];
  432.       d[Y] = preP[Y] - aktP[Y];
  433.       d[Z] = preP[Z] - aktP[Z];
  434.  
  435.       k = -aktd / (VY1[X] * d[X] + VY1[Y] * d[Y] + VY1[Z] * d[Z]);
  436.  
  437.       intP[X] = aktP[X] + k * d[X];
  438.       intP[Y] = aktP[Y] + k * d[Y];
  439.       intP[Z] = aktP[Z] + k * d[Z];
  440.  
  441.       Assign_Vector(ClipPoints[pc++], intP);
  442.     }
  443.  
  444.     if (aktd <= 0.0)
  445.     {
  446.       Assign_Vector(ClipPoints[pc++], aktP);
  447.     }
  448.  
  449.     Assign_Vector(preP, aktP);
  450.  
  451.     pred = aktd;
  452.   }
  453.  
  454.   if (((fird < 0.0) && (aktd > 0.0)) || ((fird > 0.0) && (aktd < 0.0)))
  455.   {
  456.     d[X] = firP[X] - aktP[X];
  457.     d[Y] = firP[Y] - aktP[Y];
  458.     d[Z] = firP[Z] - aktP[Z];
  459.  
  460.     k = -aktd / (VY1[X] * d[X] + VY1[Y] * d[Y] + VY1[Z] * d[Z]);
  461.  
  462.     intP[X] = aktP[X] + k * d[X];
  463.     intP[Y] = aktP[Y] + k * d[Y];
  464.     intP[Z] = aktP[Z] + k * d[Z];
  465.  
  466.     Assign_Vector(ClipPoints[pc++], intP);
  467.   }
  468.  
  469.   for (i = 0; i < pc; i++)
  470.   {
  471.     Assign_Vector(Points[i], ClipPoints[i]);
  472.   }
  473.  
  474.   if ((*PointCnt = pc) == 0)
  475.     return;
  476.  
  477.   /********** clip polygon at "top" plane **********/
  478.  
  479.   pc = 0;
  480.  
  481.   Assign_Vector(firP, Points[0]);
  482.  
  483.   fird = VY2[X] * firP[X] + VY2[Y] * firP[Y] + VY2[Z] * firP[Z] - DY2;
  484.  
  485.   if (fird <= 0.0)
  486.   {
  487.     Assign_Vector(ClipPoints[pc++], firP);
  488.   }
  489.  
  490.   Assign_Vector(aktP, firP);
  491.   Assign_Vector(preP, firP);
  492.  
  493.   aktd = pred = fird;
  494.  
  495.   for (i = pc = 0; i < *PointCnt; i++)
  496.   {
  497.     Assign_Vector(aktP, Points[i]);
  498.  
  499.     aktd = VY2[X] * aktP[X] + VY2[Y] * aktP[Y] + VY2[Z] * aktP[Z] - DY2;
  500.  
  501.     if (((aktd < 0.0) && (pred > 0.0)) || ((aktd > 0.0) && (pred < 0.0)))
  502.     {
  503.       d[X] = preP[X] - aktP[X];
  504.       d[Y] = preP[Y] - aktP[Y];
  505.       d[Z] = preP[Z] - aktP[Z];
  506.  
  507.       k = -aktd / (VY2[X] * d[X] + VY2[Y] * d[Y] + VY2[Z] * d[Z]);
  508.  
  509.       intP[X] = aktP[X] + k * d[X];
  510.       intP[Y] = aktP[Y] + k * d[Y];
  511.       intP[Z] = aktP[Z] + k * d[Z];
  512.  
  513.       Assign_Vector(ClipPoints[pc++], intP);
  514.     }
  515.  
  516.     if (aktd <= 0.0)
  517.     {
  518.       Assign_Vector(ClipPoints[pc++], aktP);
  519.     }
  520.  
  521.     Assign_Vector(preP, aktP);
  522.  
  523.     pred = aktd;
  524.   }
  525.  
  526.   if (((fird < 0.0) && (aktd > 0.0)) || ((fird > 0.0) && (aktd < 0.0)))
  527.   {
  528.     d[X] = firP[X] - aktP[X];
  529.     d[Y] = firP[Y] - aktP[Y];
  530.     d[Z] = firP[Z] - aktP[Z];
  531.  
  532.     k = -aktd / (VY2[X] * d[X] + VY2[Y] * d[Y] + VY2[Z] * d[Z]);
  533.  
  534.     intP[X] = aktP[X] + k * d[X];
  535.     intP[Y] = aktP[Y] + k * d[Y];
  536.     intP[Z] = aktP[Z] + k * d[Z];
  537.  
  538.     Assign_Vector(ClipPoints[pc++], intP);
  539.   }
  540.  
  541.   for (i = 0; i < pc; i++)
  542.   {
  543.     Assign_Vector(Points[i], ClipPoints[i]);
  544.   }
  545.  
  546.   *PointCnt = pc;
  547. }
  548.  
  549.  
  550.  
  551. /*****************************************************************************
  552. *
  553. * FUNCTION
  554. *
  555. *   Destroy_Project_Tree
  556. *
  557. * INPUT
  558. *   
  559. * OUTPUT
  560. *   
  561. * RETURNS
  562. *   
  563. * AUTHOR
  564. *
  565. *   Dieter Bayer
  566. *   
  567. * DESCRIPTION
  568. *
  569. *   Recursively destroy a node in a projection (i.e. vista/light) tree.
  570. *
  571. * CHANGES
  572. *
  573. *   Sep 1994 : Creation.
  574. *
  575. *   Dec 1994 : Fixed memory leakage due to pruned branches. [DB]
  576. *   Mar 1996 : Added COOPERATE for GUIs. [esp]
  577. *
  578. ******************************************************************************/
  579.  
  580. void Destroy_Project_Tree(Node)
  581. PROJECT_TREE_NODE *Node;
  582. {
  583.   unsigned short i;
  584.  
  585.   if (Node->is_leaf & TRUE)
  586.   {
  587.     COOPERATE_1
  588.     POV_FREE(Node);
  589.   }
  590.   else
  591.   {
  592.     for (i = 0; i < Node->Entries; i++)
  593.     {
  594.       Destroy_Project_Tree(Node->Entry[i]);
  595.     }
  596.  
  597.     POV_FREE(Node->Entry);
  598.  
  599.     POV_FREE(Node);
  600.   }
  601. }
  602.  
  603.  
  604.  
  605.